package com.ztom.top100;

/**
 * 目标和
 * <p>
 * https://leetcode-cn.com/problems/target-sum/
 *
 * @author ZhangTao
 */
public class Code92FindTargetSumWays {

    public int findTargetSumWays3(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // sum
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (target > sum) {
            return 0;
        }
        // 奇偶性一定一样
        if (((sum & 1) ^ (target & 1)) != 0) {
            return 0;
        }
        return process2(nums, 0, target);
    }

    private int process2(int[] nums, int i, int rest) {
        if (i == nums.length) {
            return rest == 0 ? 1 : 0;
        }

        return process2(nums, i + 1, rest + nums[i])
                + process2(nums, i + 1, rest - nums[i]);
    }

    public int findTargetSumWays2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // sum
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (target > sum) {
            return 0;
        }
        // 奇偶性一定一样
        if (((sum & 1) ^ (target & 1)) != 0) {
            return 0;
        }

        // sum(P) - sum(N) = target
        // sum(P) = (sum + target) / 2
        return process1(nums, 0, (sum + target) >> 1);
    }

    private int process1(int[] nums, int i, int rest) {
        if (i == nums.length) {
            return rest == 0 ? 1 : 0;
        }

        int p = process1(nums, i + 1, rest);
        if (rest >= nums[i]) {
            p += process1(nums, i + 1, rest - nums[i]);
        }
        return p;
    }

    public int findTargetSumWays1(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // sum
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (target > sum) {
            return 0;
        }
        // 奇偶性一定一样
        if (((sum & 1) ^ (target & 1)) != 0) {
            return 0;
        }

        // sum(P) - sum(N) = target
        // sum(P) = (sum + target) / 2
        int n = nums.length;
        int m = (sum + target) >> 1;
        if (m < 0) {
            return 0;
        }
        int[][] dp = new int[n + 1][m + 1];
        dp[n][0] = 1;

        for (int i = n - 1; i >= 0; i--) {
            for (int rest = 0; rest <= m; rest++) {
                dp[i][rest] = dp[i + 1][rest];
                if (rest >= nums[i]) {
                    dp[i][rest] += dp[i + 1][rest - nums[i]];
                }
            }
        }

        return dp[0][m];
    }

    public int findTargetSumWays(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // sum
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (target > sum) {
            return 0;
        }
        // 奇偶性一定一样
        if (((sum & 1) ^ (target & 1)) != 0) {
            return 0;
        }

        // sum(P) - sum(N) = target
        // sum(P) = (sum + target) / 2
        int t = (sum + target) >> 1;
        if (t < 0) {
            return 0;
        }

        int[] dp = new int[t + 1];
        dp[0] = 1;

        for (int num : nums) {
            for (int i = t; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }

        return dp[t];
    }
}
